package s9_树.tree2_顺序存储二叉树;

/**
 * @author wisdomelon
 * @date 2020/8/15 0015
 * @project data_study
 * @jdk 1.8
 */
public class ArrBinaryTreeDemo {

    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5,6,7};

        ArrBinaryTree arrBinaryTreeDemo = new ArrBinaryTree(arr);

        arrBinaryTreeDemo.preOrder(0);
        System.out.println();
        arrBinaryTreeDemo.midOrder(0);
        System.out.println();
        arrBinaryTreeDemo.postOrder(0);

    }
}

/**
 * 顺序存储二叉树
 * 1.顺序存储二叉树通常只考虑完全二叉树
 * 2.第n个元素的左子节点为2*n+1
 * 3.第n个元素的右子节点为2*n+2
 * 4.第n个元素的父节点为（n-1）/2
 * 5.n表示二叉树中的第几个元素（按0开始编号）
 *
 */
class ArrBinaryTree {

    private int[] arr;

    public ArrBinaryTree(int[] arr) {
        this.arr = arr;
    }

    /**
     * 顺序存储二叉树的前序遍历
     * @param index 数据下标
     */
    public void preOrder(int index) {

        if(arr == null || arr.length == 0 ){
            return;
        }

        // 输出当前元素
        System.out.print(arr[index]+"\t");
        // 找到当前节点的左子节点
        int leftIndex = index*2+1;
        if(leftIndex < arr.length) {
            preOrder(leftIndex);
        }

        // 找到当前节点的右子节点
        int rightIndex = index*2+2;
        if(rightIndex < arr.length) {
            preOrder(rightIndex);
        }
    }

    /**
     * 顺序存储二叉树的中序遍历
     * @param index 数据下标
     */
    public void midOrder(int index) {

        if(arr == null || arr.length == 0 ){
            return;
        }

        // 找到当前节点的左子节点
        int leftIndex = index*2+1;
        if(leftIndex < arr.length) {
            midOrder(leftIndex);
        }

        // 输出当前元素
        System.out.print(arr[index]+"\t");

        // 找到当前节点的右子节点
        int rightIndex = index*2+2;
        if(rightIndex < arr.length) {
            midOrder(rightIndex);
        }
    }

    /**
     * 顺序存储二叉树的后序遍历
     * @param index 数据下标
     */
    public void postOrder(int index) {

        if(arr == null || arr.length == 0 ){
            return;
        }

        // 找到当前节点的左子节点
        int leftIndex = index*2+1;
        if(leftIndex < arr.length) {
            postOrder(leftIndex);
        }

        // 找到当前节点的右子节点
        int rightIndex = index*2+2;
        if(rightIndex < arr.length) {
            postOrder(rightIndex);
        }

        // 输出当前元素
        System.out.print(arr[index]+"\t");
    }
}
